//单词之和
struct TireNode
{
    TireNode* _next[26];
    bool _isEnd;
    int _val;
    TireNode()
        :_isEnd(false)
        ,_val(0)
    {
        memset(_next,0,sizeof(_next));
    }
};

class MapSum {
public:
    /** Initialize your data structure here. */

    //前缀树+图
    MapSum() 
    {
        _head=new TireNode();
    }
    void insert(string key, int val) 
    {
        int num=val;
        //由于我们在每个位置存的都是全部的key值
        //所以当我们修改已经存在的值时，只能让当前节点的值加上差值
        //以满足节点对应的val是所有经过该点的key值总和

        if(hash.count(key))
        {
            num-=hash[key];     
        }
        //插入哈希表
        hash[key]=val;
        TireNode* cur=_head;
        for(auto ch:key)
        {
            if(cur->_next[ch-'a']==nullptr)
            {
                cur->_next[ch-'a']=new TireNode();
            }
            cur=cur->_next[ch-'a'];
            cur->_val+=num;
        }

    }
    
    int sum(string prefix) 
    {
        TireNode* cur=_head;
        for(auto ch:prefix)
        {
            if(cur->_next[ch-'a']==nullptr) return 0;
            else cur=cur->_next[ch-'a'];
        }
        return cur->_val;
    }
private:
    TireNode* _head;
    unordered_map<string,int> hash;
};

//最大的异或
// 如果 ai 的第 k 个二进制位为 0，那么我们应当往表示 1的子节点走，
//使得 x 的第 k 个二进制位为 1。
// 如果 ai​ 的第 k 个二进制位为 1，那么我们应当往表示 0 的子节点走，这样使
//得 x 的第 k 个二进制位为 1。

class Trie {
private:
    vector<Trie*> nexts;
public:
    Trie() : nexts(2, nullptr) 
    {}
    void insert(int num) 
    {
        Trie* curr = this;
        for (int i = 31; i >= 0; i--) 
        { 
            // 从高位开始取二进制位
            int bit = (num >> i) & 1; // 第 i 位是否为 1
            if (curr->nexts[bit] == nullptr) 
            {
                curr->nexts[bit] = new Trie();
            }
            curr = curr->nexts[bit];
        }
    }
    int XOR(int num) 
    {
        Trie* curr = this;
        int res = 0;
        for (int i = 31; i >= 0; i--) 
        {
            int bit = (num >> i) & 1;
            if (curr->nexts[!bit] != nullptr)
            { // 第 i 位上能取到反
                res |= (1 << i); // 第 i 位就为 1
                curr = curr->nexts[!bit];
            } 
            else 
            {
                curr = curr->nexts[bit]; // 否则第 i 位默认为 0
            }
        }
        return res;
    }
};

class Solution {
private:
    Trie* trie = new Trie();
public:
    int findMaximumXOR(vector<int>& nums) {
        // 先构建前缀树
        for (int num : nums) 
        {
            trie->insert(num);
        }
        // 再找最大异或
        int maxXOR = INT_MIN;
        for (int num : nums) 
        {
            maxXOR = max(maxXOR, trie->XOR(num));
        }
    return maxXOR;
    }
};